#include <vector>
using namespace std;

// 方法2 线段树
class NumArray {
  vector<int> segmentTree;
  int length;
  void buildTree(int n, int left, int right, vector<int> &nums) {
    if (left == right) {
      segmentTree[n] = nums[left];
      return;
    }
    int middle = (left + right) >> 1, left_n = 2 * n + 1, right_n = left_n + 1;
    buildTree(left_n, left, middle, nums);
    buildTree(right_n, middle + 1, right, nums);
    segmentTree[n] = segmentTree[left_n] + segmentTree[right_n];
  }

  void updateLeft(int n, int left, int right, int index, int val) {
    if (left == right) {
      segmentTree[n] = val;
      return;
    }
    int middle = (left + right) >> 1, left_n = 2 * n + 1, right_n = left_n + 1;
    if (index <= middle) {
      updateLeft(left_n, left, middle, index, val);
    } else {
      updateLeft(right_n, middle + 1, right, index, val);
    }
    segmentTree[n] = segmentTree[left_n] + segmentTree[right_n];
  }

  int sumRange(int n, int my_left, int my_right, int left, int right) {
    if (left <= my_left && my_right <= right) {
      return segmentTree[n];
    }

    int middle = (my_left + my_right) >> 1, left_n = 2 * n + 1,
        right_n = left_n + 1, res = 0;
    if (left <= middle) {
      res += sumRange(left_n, my_left, middle, left, right);
    }
    if (right > middle) {
      res += sumRange(right_n, middle + 1, my_right, left, right);
    }
    return res;
  }

public:
  NumArray(vector<int> &nums) {
    length = nums.size();
    segmentTree.resize(4 * length);
    buildTree(0, 0, length - 1, nums);
  }

  void update(int index, int val) { updateLeft(0, 0, length - 1, index, val); }

  int sumRange(int left, int right) {
    return sumRange(0, 0, length - 1, left, right);
  }
};
